#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
using namespace std;

// West bank or east bank.
// Content of the State array.
enum {
  West,
  East,
};

typedef bool State[4];           // Holds bank info of each character.
typedef queue<unsigned> Queue;   // contains hash value of states.
typedef map<unsigned, int> Map;  // hash value to state id (start from 1).

// Four characters. Indices into State array.
enum {
  Farmer,
  Wolf,
  Goat,
  Cabbage,
};

Map StateMap;

// State deflation.
unsigned Hash(State& s) {
  unsigned ans = 0;
  for (unsigned i = 0; i < 4; ++i) {
    ans |= s[i] << i;
  }
  return ans;
}

// State inflation.
void Unhash(int h, State& out) {
  unsigned mask = 1;
  for (int i = 0; i < 4; ++i) {
    out[i] = h & mask;
    mask <<= 1;
  }
}

// Whether this state is invalid (someone being eaten with absence of the
// farmer).
bool InvalidState(State& s) {
  if (s[Cabbage] == s[Goat] && s[Cabbage] != s[Farmer]) {
    return true;
  }
  if (s[Wolf] == s[Goat] && s[Wolf] != s[Farmer]) {
    return true;
  }
  return false;
}

// Init to be all east.
void InitState(State& s) {
  for (int i = 0; i < 4; ++i) {
    s[i] = East;
  }
}

// Whether it is all west.
bool IsEndState(State& s) {
  for (int i = 0; i < 4; i++) {
    if (s[i] == East) return false;
  }
  return true;
}

// Print the edge `now_id -> nxt`. If `nxt` is a new state (not discovered
// before), it is registered and pushed into the queue.
void Enqueue(int now_id, State& nxt, Queue& Q) {
  unsigned h = Hash(nxt);
  int id;

  if (StateMap.count(h)) {
    // Duplicate state.
    id = StateMap[h];
    printf("%d -> %d\n", now_id, id);
    return;
  }
  Q.push(h);
  id = StateMap.size() + 1;  // 0 is invalid id.
  StateMap[h] = id;
  printf("%d -> %d\n", now_id, id);
}

// Generate and print states reachable from `now`.
void FindNext(State& now, Queue& Q) {
  int now_id = StateMap.at(Hash(now));
  now[Farmer] = !now[Farmer];
  Enqueue(now_id, now, Q);
  for (int i = 1; i < 4; ++i) {
    int temp = now[i];
    if (temp != now[Farmer]) {
      now[i] = now[Farmer];
      Enqueue(now_id, now, Q);
      now[i] = temp;
    }
  }
}

// BFS algorithm to discover the state digraph.
void SeachStates() {
  State s;
  InitState(s);
  unsigned h = Hash(s);
  StateMap[h] = 1;
  Queue Q;
  Q.push(h);

  while (!Q.empty()) {
    h = Q.front();
    Q.pop();
    Unhash(h, s);
    if (IsEndState(s) || InvalidState(s)) {
      continue;
    }
    FindNext(s, Q);
  }
}

// Print out all detailed information about all states (nodes).
void PrintStates() {
  // Reverse the StateMap for ease of handling.
  map<int, unsigned> revmap;
  for (auto&& p : StateMap) {
    revmap[p.second] = p.first;
  }
  for (auto&& p : revmap) {
    printf("%d:", p.first);
    State s;
    Unhash(p.second, s);
    for (int i = 0; i < 4; ++i) {
      bool loc = s[i];
      printf(" %s", loc == West ? "W" : "E");
    }
    // Whether this is an end/invalid state.
    if (IsEndState(s)) {
      puts(" end");
    } else if (InvalidState(s)) {
      puts(" inv");
    } else {
      puts("");
    }
  }
}

int main() {
  SeachStates();
  PrintStates();
  return 0;
}